/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 周斌
 * Date: 2024-01-19
 * Time: 21:48
 */
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //1.判断p或q是否为root
        if(root == null || p == root ||q == root) {
            return root;
        }
        //2.遍历左子树，寻找q或p
      TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
        //3.遍历右子树，寻找q或p
        TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
        //两边都不为空
        if(leftTree != null && rightTree !=null) {
            return root;
        }
        //一边不为空
        else if(leftTree !=null) {
            return leftTree;
        } else {
            return rightTree;
        }
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode();
    }
}
